The prior art discloses various arrangements of data processing systems employing a virtual memory approach for storing information which is used and/or processed by the system. Virtual memory arrangements currently employed in the art generally involve a relatively small capacity semiconductor memory which is fast, and a relatively large capacity storage device, such as a disk drive which is relatively inexpensive storage, but relatively slow. The small capacity memory is made to appear quite large to the system by means of a paging mechanism which functions to transfer data between the two separate storage entities so that the information required by the system is always available in real memory. The transfer of data is referred to as "paging," in that the data is transferred in blocks or "pages," each of which is generally a fixed size, such as 2048 (2k) bytes. The mechanism for controlling the paging operation is usually referred to as the paging mechanism or paging subsystem.
The paging mechanism causes a page of data to be paged into real memory in response to the occurrence of a page fault. A page fault occurs when the system requests data that is not in real memory. The page fault mechanism which functionally is usually part of the overall memory management unit determines that the requested data is not in real memory, and initiates the paging operation. A page fault causes the program that is being executed, often referred to as a "process," to be halted until the page fault is resolved by paging in the required data. In a single user/single application environment, page faults have a direct impact on the overall system performance. If, however, the system is capable of running more than one process concurrently, the adverse effect of a page fault is decreased, since another process can be dispatched by the system while the one interrupted process is waiting for its page fault to be resolved.
One aspect in the design of a virtual memory systems involves the manner in which addressing is handled. The "real memory" which interfaces directly with the system is generally addressable at a byte level. As a result, the number of byte storage locations or addresses is, therefore, equivalent to the storage capacity of the real memory, and determines the number of bits required in the address. For example, a 64k memory requires a 16 bit address, in that 2*(16) [2 to the exponent 16]=64K (65,536) whereas a 1 megabyte memory requires a 20 bit address to address each of its locations 2*(20)=1 megabyte of memory or 1 million addresses).
The virtual memory address space is generally much, much larger than the real memory address space.
One technique used by many virtual memory systems to generate a virtual address is referred to as "paged segmentation." Assume for example that the address space has 2*(40) separate address locations. In the paged segmentation technique, the effective address space of the virtual memory is divided into, for example, 16 separate equal-sized memory segments by the memory management unit. Each segment is represented or addressed by a 12 bit memory segment identifier which is contained in one of 16 segment registers. Four bits of the 32 bit effective address from the processor are used to select one of the 16 segment registers to provide the 12 bit memory segment identifier, which is concatenated with the remaining 28 bits (32-4) of the effective address which is used as the segment offset. Under the above assumptions the byte capacity of the virtual memory is 2*(40).
In order to assign and manage addressing operations, many systems provide three primary data structures associated with the memory management unit. They are the Segment Table (ST), the External Page Table (XPT) and the Inverted Page Table (IPT).
The Segment Table defines the objects that can be referenced by the system, an object being, for example, a complete program, a mapped file, or computational data. The Segment Table contains information such as the segment size and the start of the segment's External Page Table. The Segment Table contains one entry for each object defined in memory. The ST is stored in real memory and is not pageable.
An External Page Table (XPT) is provided for each segment. One entry in the table comprises four bytes and describes characteristics of the associated page, such as its location on the disk and protection-type information for that page. If the segment contains 100 pages, its XPT will contain 100 entries and will be 400 bytes in size. The XPT is pageable by the system.
The External Page Tables, per se, are stored at virtual addresses which are part of the segment that contains the program for managing system resources, generally referred to as the Virtual Resource Manager (VRM). The VRM segment in memory includes a pool of External Page Tables, and since each segment in the system requires an XPT, the XPT for the VRM segment is also stored in this pool. Since the XPT for the VRM segment contains a separate four byte entry for each page of the VRM segment, a subset of the four byte entries for each VRM segment's External Page Table defines the External Page Tables for the other segments. This section, or subset, of the XPT for the VRM segment is referred to as the "XPT of the XPT," and is not pageable.
The third important data structure employed is the Inverted Page Table (IPT). Real memory is divided into page frames, corresponding in size to pages in the virtual address space, i.e., 2k. A page frame in real memory is, therefore, a container for one virtual page. The function of the IPT is, therefore, merely to identify the virtual page that is currently in each page frame of real memory. Each entry in the IPT is 32 bytes long. The IPT is not pageable.
The memory manager uses the IPT information in translating a virtual address into a real address and signals a page fault when a requested virtual page is not contained in the IPT.
As the speed and computing power of processing units increases, and the cost for a byte of storage and access time decreases, there is a desire and trend to provide larger virtual memories to handle larger and more complex applications. This results in the various objects that are stored in virtual memory, requiring larger and larger segments, i.e., more pages. It is assumed that in this discussion, a large segment contains at least one megabyte of storage space. Depending on the object, the segment may be completely filled with data, or sparsely filled. For reference purposes, a sparse segment is defined as one which contains at least one unreferenced region that is large enough to contain a storage area that can be defined by at least one page of XPT entries. At 4 bytes per entry, 1 page of xpt entries covers 512 virtual pages or a 1 megabyte address space.
There are several virtual memory operations that perform an operation on an entire segment, such as create segment, copy segment, change segment size, and destroy segment. Services of this type should support large segments without a significant system performance penalty. This goal is difficult to achieve, because the size of a segment's XPT is proportional to the size of the segment and, therefore, a large segment has a large XPT. For example, a 256 megabyte segment has 131,072 XPT entries. This requires 256 pages in the pool of XPT entries that is part of the VRM segment. An XPT entry defines 2,048 bytes of virtual memory. A page of XPT entries contains 512 XPT entries, and defines one megabyte of virtual memory. Therefore, 256 pages of XPT entries are required to define a 256 megabyte segment.
The prior art virtual memory systems do not provide a solution to the adverse impact on the system that is experienced when the system must operate on a very large number of pages, e.g. more than 512 pages. Accessing this large an amount of data can result in significant overhead, due to the number of instructions executed, the number of pages referenced, and the number of page faults resulting from these references.
The present invention describes a method to overcome the shortcomings of the prior art in operating on large data segments in a virtual memory environment.